export const searchBinary = (array: number[], itemSearch: number): number | undefined => {
  const len = array.length;
  let index;

  let iStart = 0;
  let iEnd = len - 1;

  while(index === undefined && iStart <= iEnd) {
    const half = Math.ceil((iStart + iEnd) / 2);
    for (let i = iStart; i <= half; i++) {
      if (array[i] === itemSearch) {
        index = i;
        break;
      }
    }
    iStart = half + 1;
  }

  return index ?? undefined;
};

export const searchBinarySortable = (array: number[], itemSearch: number): number | undefined => {
  const len = array.length;
  let half = Math.ceil(len / 2);
  let halfV = array[half];
  let index;

  let iStart = 0;
  let iEnd = array.length - 1;
  
  while(index === undefined && iStart < iEnd) {
    if (halfV === itemSearch) {
      index = half;
    } else {
      let newHalf;
      
      if (halfV < itemSearch) {
        iStart = half + 1;
        newHalf = Math.ceil((iEnd + iStart) / 2);
      } else {
        iEnd = half - 1;
        newHalf = Math.floor((iEnd + iStart) / 2);
      }
      
      half = newHalf;
      halfV = array[newHalf];
    }
  }

  return index ?? -1;
};

export const searchBinaryRecursion = (array: number[], itemSearch: number, options: {
  iStart: number;
  iEnd: number;
}): number | undefined => {
  const { iStart, iEnd } = options;
  let index;
  let half = Math.ceil((iStart + iEnd) / 2);
  let halfV = array[half];
  
  if (iStart < iEnd && index === undefined) {
    if (itemSearch > halfV) {
      index = searchBinaryRecursion(array, itemSearch, {
        iStart: half + 1,
        iEnd
      });
    } else if (itemSearch < halfV) {
      index = searchBinaryRecursion(array, itemSearch, {
        iStart,
        iEnd: half - 1
      });
    } else {
      index = half;
    }
  } else {
    if (itemSearch === halfV) {
      index = half;
    } else {
      index = undefined;
    }
  }

  return index ?? undefined;
};
